/*
    Wing Kuang (wwk3j) / Michael Dewey-Vogt (mkd5m)
    April 16, 2012
    CS4414, Lab 7


    NOTE: This code requires that CHAR_BIT is 8 and sizeof(int) == 4.
    I didn't bother mucking around with static asserts, but that would be
    best-practice here.
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_FILES 1024

#define BLOCK_SIZE 1024

#define INDEX_LENGTH (BLOCK_SIZE/(int)sizeof(int))

#define N_DBLOCKS 12 
#define N_IBLOCKS 3

#define EXIT_ERROR 1


/*
    Struct used to hold a single block of data.
*/
typedef struct {
    char bytes[BLOCK_SIZE];
} data_block_t;

/*
    Helper struct used to pass around variables which would otherwise have
    to be global or passed individually.
*/
typedef struct {
    bool* used_blocks; //keeps track of which data blocks have been discovered by our algorithm
    FILE* out_file; //the handle of the current open found file being written
    int file_size; //total size of the datafile in bytes
    int block_counter;//stores the number of remaining blocks to be written
} inode_helper_t;


/*
    Given inode struct from the problem definition.
*/
typedef struct {
    int foo; //Unknown
    int nlink; //Number of links to this file
    int uid; //Owner's user ID
    int gid; //Owner's group ID
    int size; //Number of bytes in file
    int ctime; //Time field
    int mtime; //Time field
    int atime; //Time field
    int dblocks[N_DBLOCKS]; //Pointers to data blocks 
    int iblocks[N_IBLOCKS]; //Pointers to indirect blocks 
    int i2block; //Pointer to doubly indirect block
    int i3block; //Pointer to triply indirect block
} inode ;

// integer divide, rounding up
// requires a > 0, b > 0
int div_up(int a, int b) {
    return a/b + (a%b==0? 0 : 1);
}

/*
    Opens the given file and quits if the open failed.
*/
FILE* try_open(char* filename, char* mode) {
    FILE* file = fopen(filename, mode);
    if (file == NULL) {
        printf("Failed to open file \"%s\".\n", filename);
        exit(EXIT_ERROR);
    }
    return file;
}

/*
    Returns the number of inodes found and populates the indexes array with
    the offset of each inode.
*/
int get_inode_indexes(int* indexes, char* data, inode_helper_t* helper, int uid, int gid) {
    bool found_uid = false;
    int count = 0;
    for (int k = 0; k < 4; k += 1) {
        for (int i = 0; i < helper->file_size/4; i += 1) {
            int* cast = (int*)(data + i*4 + k);
            int next = *cast;
            if (found_uid) {
                if (next == gid) { 
                    int index = i + k - 3;
                    if (k != 0) {
                        printf("Detected inode not aligned to 4-byte words at address %d, which currently cannot be handled\n", index);
                        exit(EXIT_ERROR);
                    }
                    indexes[count++] = index;
                } else {
                    found_uid = false;
                }
            }
            if (next == uid) {
                found_uid  = true;
            }  
        }
    }
    if (count == 0) {
        printf("No files with the given uid/gid pair found.\n");
        exit(EXIT_ERROR);
    }
    return count;
}

/*
    This function verifies that each found block is not larger than the size of our
    data file, as this would represent an error in our algorithm.
*/
void test(int i, int file_size) {
    i = i * BLOCK_SIZE;
    if (i > file_size || i < 0) {
        printf("%d too large for file size - algorithmic error\n", i);
        exit(EXIT_ERROR);
    }

}

void register_block(char* data, inode* node, int block_index, inode_helper_t* helper) {
    helper->used_blocks[block_index] = true;
    test(block_index, helper->file_size);
    int size = BLOCK_SIZE;
    if (helper->block_counter == 1) {
        size = node->size % BLOCK_SIZE;
    } 
    
    data_block_t* block = (data_block_t*)(data + block_index*BLOCK_SIZE); 
    fwrite(block, size, 1, helper->out_file);
    helper->block_counter--;
}

int* seek_block(char* data, int offset, inode_helper_t* helper) {
    test(offset, helper->file_size);
    return (int*)(data + offset*BLOCK_SIZE);
}

void gather_blocks(char* data, inode* node, inode_helper_t* helper) {
    int num_blocks = div_up(node->size,BLOCK_SIZE);
    helper->block_counter = num_blocks;
    
    //printf("_____FILE_____\nD block accessed\n");
    for (int i = 0; i < N_DBLOCKS; i++) {
       register_block(data, node, node->dblocks[i], helper);
           
       if (helper->block_counter <= 0) return;
    }
    //printf("I block accessed\n");
    for (int i = 0; i < N_IBLOCKS; i++) {
        int* dblocks = seek_block(data, node->iblocks[i], helper);
        
        for (int j = 0; j < INDEX_LENGTH; j++) {
            register_block(data, node, dblocks[j], helper);
            if (helper->block_counter <= 0) return;
        }
    }
    //printf("doubly indirect accessed\n");
    int* iblock = seek_block(data, node->i2block, helper);
    for (int i = 0; i < INDEX_LENGTH; i++) {
        int* iiblock = seek_block(data, iblock[i], helper);
        
        for(int j = 0; j < INDEX_LENGTH; j++) {
            register_block(data, node, iiblock[j], helper);
            if (helper->block_counter <= 0) return;
        }
    }
    
    //printf("triply indirect accessed\n");
    /// ***UNTESTED*** 
    /// TRIPLY INDIRECT INODE
    int* i3_ptr = seek_block(data, node->i3block, helper);
    for (int i = 0; i < INDEX_LENGTH; i++) {
        int* i2_ptr = seek_block(data, i3_ptr[i], helper);
        
        for(int j = 0; j < INDEX_LENGTH; j++) {
            int* i1_ptr = seek_block(data, i2_ptr[j], helper);
            
            for(int k = 0; k < INDEX_LENGTH; k++) {
                register_block(data, node, i1_ptr[k], helper);
                if (helper->block_counter <= 0) return;
            }
        }
    }

    
    printf("File is too large for current algorithm.\n");
    exit(EXIT_ERROR);
}

int get_file_size(FILE* file) {
    fseek(file, 0, SEEK_END);
    int size = ftell(file);
    rewind(file);
    return size;
}

/*
    Writes all of the unused chunks to a flat textfile.
*/
void write_unused(int num_blocks, inode_helper_t* helper) {
    FILE* unused = try_open("unused.txt", "w");
    char buffer[100];
    for (int i = 0; i < num_blocks; i += 1) {
        if (!helper->used_blocks[i]) {
            sprintf(buffer, "%d", i);
            fprintf(unused, "%s\r\n", buffer);
        }
    }
    fclose(unused);
}

/*
    Parse command line arguments.
*/
char* parse_args(int argc, char** argv, int* suspected_uid, int* suspected_gid) {
    if (argc < 4) {
        printf("Usage is ./extract <datafile> <suspected_uid> <suspected_gid>\n");
        exit(EXIT_ERROR);
    }
    char* filename = argv[1];
    *suspected_uid = atoi(argv[2]);
    *suspected_gid = atoi(argv[3]);
    return filename;

}

int main(int argc, char** argv) {
    int suspected_uid, suspected_gid;
    char* filename = parse_args(argc, argv, &suspected_uid, &suspected_gid);
    
    inode_helper_t helper;

    FILE* data_file = try_open(filename, "rb");
    helper.file_size = get_file_size(data_file);
    char* data = malloc(sizeof(char) * helper.file_size);
    fread(data, sizeof(char), helper.file_size, data_file);
    fclose(data_file);
    
    int num_blocks = div_up(helper.file_size, BLOCK_SIZE);
    
    helper.used_blocks = malloc(sizeof(bool) * num_blocks);
    for (int i = 0; i < num_blocks; i += 1) {
        helper.used_blocks[i] = false;
    }
    

    int* indexes = malloc(sizeof(int)*MAX_FILES);
    
    int num_inodes = get_inode_indexes(indexes, data, &helper, suspected_uid, suspected_gid);
    
    char out_filename[256];
    for (int i = 0; i < num_inodes; i++) {
        inode* mynode = (inode*)(data + indexes[i] * 4);
        sprintf(out_filename, "%05d.file", i);
        helper.out_file = try_open(out_filename, "wb");
        gather_blocks(data, mynode, &helper);
        fclose(helper.out_file);
    }
    
    write_unused(num_blocks, &helper);
    return 0;
}
